今天來講講常見的小品序列問題——如果變成了環狀該怎麼辦。大致的想法就是想辦把找到突破口，然後把它拆成數個小題目，每一個小題目都是一般的直線序列問題。

Exercise 21: Leetcode 213 - House Rubber II

題目連結

https://leetcode.com/problems/house-robber-ii/

題目敘述

給你一個繞成一圈的序列，你想要挑一些數字拿走，但是不能拿相鄰的兩個數字（包含首尾）請問能夠拿走得數字組合中，可能的最大總和是多少？

比方說 [2, 3, 2] 繞成一圈，任何一個都與剩下兩個相鄰，因此你只能挑一個：那只能選 3 達到最大總和。

解題思考

我們可以枚舉第一個數字到底有沒有被用到，如果有的話，剩下就是一個從 index=2 ~ index=n-2 之間的「序列問題」。如果沒有的話，剩下就是一個從 index=1 ~ index=n-1 之間的序列問題。換言之，只要我們會做序列問題，就能夠解決這個環狀問題啦！

至於序列問題 (Leetcode 198) 怎麼做，這個問題非常地費氏數列，就交給大家自行參考囉～

參考程式碼 (Python3)

class Solution:
    def solve_line(self, nums: List[int]) -> int:
        if len(nums) > 1:
            nums[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            nums[i] = max(nums[i] + nums[i-2], nums[i-1])
        return nums[-1] if len(nums) > 0 else 0

    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        pick = nums[0] + (self.solve_line(nums[2:-1]) if len(nums) > 2 else 0)
        dont = self.solve_line(nums[1:])
        return max(pick, dont)

另一種樣貌的環狀陣列，也可以透過有趣的互補法來解題。

Exercise 22: Leetcode 918 - Maximum Sum Circular Subarray

題目連結

https://leetcode.com/problems/maximum-sum-circular-subarray/

題目敘述

給你一個環狀陣列，請找出其中一段連續的格子，使得他們的總和最大。

解題思考

如果我們採用前一題的作法：考慮這段連續格子包含第一格、或不包含第一格。那麼在不包含第一格的情形下，作法會與原題目相同。但是在包含第一格的情況下，仍有可能最後會拆成兩段啊，與原題目「找一段連續格子」並不相同！

但是，我們可以使用互補思考法，可以發現：在連續格子必須包括第一格的情形下，那些沒有被選取的格子們恰好行程連續的一個片段！因此整題可以轉換成「找出一段最小的連續格子和（或0）」，就解決啦！

如果你說「哎唷我已經寫了一個找最大連續和的函式了，不要再寫一個最小值的版本」，那其實我們可以把傳入的陣列全部取個負號，那最小值就變成最大值啦～

參考程式碼 (Python3)

class Solution:
    def maxSubarraySum(self, A: List[int]) -> int:
        now, best = 0, float("-inf")
        for x in A:
            now += x
            best = max(best, now)
            now = 0 if now < 0 else now
        return best

    def maxSubarraySumCircular(self, A: List[int]) -> int:
        if len(A) == 1:
            return A[0]
        drop = self.maxSubarraySum(A[1:])
        pick = sum(A) + max(0, self.maxSubarraySum([-x for x in A[1:]]))
        return max(drop, pick)

備註

解決一般 maxSubarraySum 的方法不一定要用 DP，也可以使用 Kadane 演算法。

總覺得今天這兩題擺在一起寫，是一件很有趣的事情：一題是最大不連續和另一題是最大連續和。下次應該多放幾題像是最不大連續和、最連續不大和、不最大連續和、不連續最大不和、大不了不最大不連續和…